1) Field of the Invention
The field of the present invention relates to electronic design automation for chip design and, more particularly, to computer-implemented methods, systems and/or products for database construction and management useful for electronic design automation applications.
2) Background
Chip designers often use electronic design automation (EDA) software tools to speed up the design process and to allow simulation of a chip design prior to prototyping or production. Chip design using EDA software tools generally involves an iterative process whereby the chip design is gradually perfected. In a typical chip design process using EDA software tools, the chip designer builds up a circuit by inputting information at a computer workstation generally having high quality graphics capability so as to display portions of the circuit design as needed. A top-down design methodology is usually employed using hardware description languages (HDLs), such as Verilog(copyright) or VHDL, for example, by which the designer creates an integrated circuit by hierarchically defining functional components of the circuit, and then decomposing each component into smaller and smaller components.
Two of the primary types of components used in integrated circuits are datapaths and control logic. Control logic, typically random logic, is used to control the operations of datapaths. Datapath areas of the circuit perform functional operations, such as mathematical or other operations. More particularly, datapaths are typically composed of large numbers of highly regular and structured datapath functions, each such function typically including an arrangement of logic cells. In large integrated circuit designs, the number of logic cells can be enormousxe2x80x94on the order of millions. The logic cells, and the information relating to them, is kept track of using a very large database.
The various components of an integrated circuit are initially defined by their functional operations and relevant inputs and outputs. The designer may also provide basic organizational information about the placement of components in the circuit using floorplanning tools. During these design states, the designer generally structures the circuit using considerable hierarchical information, and has typically provided substantial regularity in the design.
From the HDL description, the actual logic cell implementation is typically determined by logic synthesis, which converts the functional description of the circuit into a specific circuit implementation. The logic cells are then placed (i.e., given specific coordinate locations in the circuit layout) and routed (i.e., wired or connected together according to the designer""s circuit definitions). The placement and routing software routines generally accept as their input a flattened netlist that has been generated by the logic synthesis process. This flattened netlist identifies the specific logic cell instances from a target standard cell library, and describes the specific cell-to-cell connectivity.
Further explanation of a particular chip design process, with particular emphasis on placement and routing of datapaths, is set forth, for example, in U.S. Pat. No. 5,838,583, hereby incorporated by reference as if set forth fully herein.
While EDA software tools provide substantial assistance to chip designers, the demands on such software tools has dramatically increased over the years as the number of components that can be fit on a single microchip has likewise increased. One aspect of such software tools that has particularly been strained is the database that is required to keep track of all of the myriad components and connections used in a chip design. The database is needed to store, among other things, the type and content of each cell (known as instances), its connections to other cells, and its location within the chip layout. Where hundreds of thousands, or millions, of cells are required for a given integrated circuit design, the database for storing such information can become quite large.
One conventional way of implementing a database for storing chip design information is to create a series of individually allocated chunks of memory, referred to as xe2x80x9cbeadsxe2x80x9d, and to link these beads dynamically with pointers. Such a database design is convenient from the standpoint of ease of varying the number of elements, since adding new elements simply involves adding more records to a linked list (or circular list) of like records. However, pointer list database designs have several drawbacks. A major disadvantage is that pointers take up a great deal of memory space. Since pointers are generally required to reach any point in working memory, for large working memories the pointers need to be relatively long. Currently, pointers are often four bytes (32 bits) in length. Where millions of cells are present in a chip design, cross-referencing information through pointers therefore can consume huge amounts of memory.
An additional disadvantage of pointer list databases is that they can take a long time to read into working memory. This problem arises because when the database is stored on a disk (or other permanent storage medium), the pointer values are not recorded since they will have different values each time the data is read in from the disk. Thus, when the database is read from the disk into working memory space, pointer values need to be assigned. The assignment of pointer values upon being read is known as pointer set-up, and the account of time needed for carrying out this process can be quite long for large databases. Where numerous design changes are made, which is a frequent occurrence with large, complicated chip designs, the pointer set-up time is endured each time the database is read from disk, which can greatly slow down the design process.
Yet another disadvantage with pointer list databases in EDA applications is that temporary data associated with a particular bead cannot easily be accessed unless space is permanently allocated within the bead. To provide for such temporary data storage and manipulation, a single generic work field, which the programmer is generally allowed to use for any purpose, is often allocated in the bead. Usually, the generic work field is used for a pointer to additional data. To provide many or all records with a generic work field generally requires setting aside a large amount of storage space, many of which may go unused and therefore be wasteful.
Since data is accessed by pointer lists, it is possible to end up with completely isolated chunks of memory, which are impossible to access using the pointer lists. This situation leads to inefficient use of memory resources.
Another disadvantage of pointer list databases is that this format as stored on the disk is usually different from their in-memory format (i.e., after the database is read in to working memory). The data beads are generally read into working memory in bits and pieces, or else they can be read in singly. In the latter case, backward compatibility with older versions of the database becomes a nuisance and inevitably slows down the read process. In addition, substantial care must be taken at the design stage, since it is often difficult to add extra pointers and data fields after the database design has been set.
Another type of conventional database is based on a series of records stored sequentially in an array. However, array-based databases for storing chip design data have not been utilized extensively in electronic design automation applications. One possible reason for the unpopularity of array-based databases in chip design applications is that such databases are commonly viewed as inefficient for handling large aggregates of data. Typically, the same amount of memory space must be allocated in advance for each record, yet the amount of data within each record can vary widely. From a programming standpoint, it can be unwieldy to handle data stored in an array-based database. Furthermore, dynamic size changes to an array-based database structure are difficult. Another drawback is that there is difficulty inserting new records anywhere but the end of the array.
It would therefore be advantageous to provide a database especially suited for chip design applications, which overcomes one or more of the foregoing problems.
The present invention relates to computer-implemented methods, systems and/or products for providing a database particularly useful for electronic design automation applications.
In one embodiment as described herein, a database for storing chip design information comprises a plurality of parallel arrays. One or more parallel arrays are used for storing a particular class of information. In this context, a class is an abstract data type comprising a collection of data, such as integers or characters, possibly in connection with a set of special functions (member functions) for operating on the collection of data. For many chip designs, there may be a hundred or more classes of information. The union of related entries commencing at a given array index across the one or more parallel arrays of a particular class forms the structure for a given instance within a class. Between classes, individual records in an array may cross-reference, through an array index, records in other arrays. For example, the database may include an array of port records in one class and a separate array of associated net records in another class, wherein each port record refers to the net assigned to it by an index number into the array of net records. A union of entries across classes that are cross-referenced together with array indexes may form a complete structure for a cell instance or other type of system component.
Due to the general absence of pointers, and the use of array indexes in their stead, large savings of memory are possible. Also, the version of the database as stored on disk or in other permanent storage medium can be almost exactly the same as the version stored in working memory (i.e., the xe2x80x9cin-memoryxe2x80x9d version). Another advantage of the array-based database structures described herein is that the record arrays can be written to disk and read from disk with a single operating system call for each array, providing increased speed of performance. Moreover, since each record set is of a known size, it is possible to quickly step over those arrays which are not needed, making read-on-demand capability relatively easy to implement.
Further memory savings and speed advantages may be obtained in other embodiments of the invention, wherein the inherent sequential nature of records stored in the array is used as linking information, thus avoiding the requirement of storing such information in memory. For example, the ports on a cell can be assumed to be in the same order as the port definitions on the corresponding cell master. As a result, a cross-referencing index from the port instance array to the port master array need only be provided to the first entry in each array, and it can be assumed that each subsequent port instance or port definition follows sequentially for the given cell.
Another technique for saving memory space is to avoid storing all of the coordinate or spatial information for a given shape, but rather to store only the offset information from the preceding shape. In one embodiment, an assumption is made that the second shape starts at the ending point of the first shape. The system can also provide certain default values or characteristics for information within the array records, with the default values being used unless overridden by an indicator in the array record. Since little or no information needs to be stored where the default values are used, memory storage requirements can be substantially reduced.
As another technique for conserving memory in connection with the usage of parallel arrays as described above, the one or more parallel arrays within a given class may adaptively allocate storage space for data entries based on the size of the data to be stored. In a particular embodiment, from one to four bytes of data (or a xe2x80x9cnullxe2x80x9d designator) may be adaptively allocated for storing data entries. The selection of allocation size may be determined by the largest value of the stored entries. The resulting array structure may be referred to as an intelligent integer array. Alternatively, one of the one or more parallel arrays in a given class may be a xe2x80x9cbytestreamxe2x80x9d encoded array, wherein a header code for a given data entry within the bytestream encoded array indicates the number of bytes following the header code for that data entry.
In a particular embodiment as disclosed herein, in which the above parallel array techniques are utilized, a database head comprises a set of pointers to a plurality of memory blocks (i.e., beads), each of which comprises a plurality of records in the form of one or more parallel arrays. Several databases may be stored in working memory at the same time, and a separate database head may be provided for each database. The database heads themselves may be connected to one another through pointers in a linked list.
In a preferred embodiment, each class has a data header with a field indicating the number of indexes allocated for each of the one or more parallel arrays and another field indicating the actual number of indices used within the one or more parallel arrays. In addition, the data header of a given class preferably includes a pointer indicating the position in memory of a main data header. Because the main data header in turn has a pointer to the position in memory of the other classes, instances in the given class may refer to related instances in the other classes through an integer index number without requiring the use of other pointers.
Further embodiments, variations and enhancements are also described herein or shown in the accompanying drawings.